from typing import Optional, List


def quicksort(num: List, left, right):
    if left > right:
        return
    i, j = left, right
    benchmark = num[left]
    while i < j:
        while num[j] >= benchmark and i < j:
            j -= 1

        while num[i] <= benchmark and i < j:
            i += 1
        exchange(num, i, j)
    if i == j:
        exchange(num, left, j)
    quicksort(num, i + 1, right)
    quicksort(num, left, j - 1)


def exchange(num: List, i, j):
    num[i], num[j] = num[j], num[i]


num = [4,65,6,1,2,3,9,8,7]
# num = [9, 8, 7, 6, 5, 4, 3, 2, 1]
quicksort(num, 0, len(num) - 1)
print(num)
